package newcoder;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;


public class NC124 {
    /**
     *
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        // write code here
        Trie trie = new Trie();
        ArrayList<String> res = new ArrayList<>();
        for(String[] x:operators){
            if("1".equals(x[0])){
                trie.insert(x[1]);
            }else if("2".equals(x[0])){
                trie.delete(x[1]);
            }else if("3".equals(x[0])){
                if(trie.search(x[1])){
                    res.add("YES");
                }else{
                    res.add("NO");
                }
            }else{
                res.add(String.valueOf(trie.prefixNumber(x[1])));
            }
        }
        String[]ans = new String[res.size()];
        int t = 0;
        for(String x:res){
            ans[t++] = x;
        }
        return ans;
    }
    class Trie{
        HashMap<String,Integer> map;
        LinkedList<String> list;
        public Trie(){
            this.map = new HashMap<>();
            this.list = new LinkedList();
        }
        void insert(String word){
            if(!map.containsKey(word)){
                list.add(word);
            }
            map.put(word,map.getOrDefault(word,0)+1);
        }//：添加word，可重复添加；
        void delete(String word){
            if(map.containsKey(word)&&map.get(word)>1){
                map.put(word,map.get(word)-1);
            }else if(map.containsKey(word)&&map.get(word)==1){
                map.remove(word);
                for(String s:list){
                    if(s==word){
                        list.remove(s);
                        return;
                    }
                }
            }
        }//：删除word，如果word添加过多次，仅删除一次；
        boolean search(String word){
            return map.containsKey(word);
        }//：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；
        int prefixNumber(String pre){
            int res=0;
            for(String s:list){
                if(s.matches(pre+".*")) res += map.get(s);
            }
            return res;
        }//：返回以字符串pre作为前缀的单词数量。
    }


    public static void main(String[] args) {
        NC124 nc  = new NC124();
        String[][] a= new String[][]{{"1","qwer"},{"1","qwe"},{"3","qwer"},{"4","q"},{"2","qwer"},{"3","qwer"},{"4","q"}};
        String[] b = nc.trieU(a);
        System.out.println(b);
    }
}